题解 CF718C 【Sasha and Array】

发表于 | 更新于

##

  • 在本题中，我们用 $f_i$ 来表示第 $i$ 个斐波那契数（$f_1=f_2=1,f_i=f_{i-1}+f_{i-2}(i\ge 3)$）。

  • 给定一个 $n$ 个数的序列 $a$。有 $m$ 次操作，操作有两种：

    1. 将 $a_l\sim a_r$ 加上 $x$。
    2. 求 $\displaystyle\left(\sum_{i=l}^r f_{a_i}\right)\bmod (10^9+7)$。

  • $1\le n,m\le 10^5$，$1\le a_i\le 10^9$。

快速求$Fibonacci$第$n$项的方法是用矩阵乘法，即原始矩阵$\begin{pmatrix} 2\ 1 \end{pmatrix}$*$Fibonacci$矩阵$^{(n-2)}$,所以我们可以想到将$n$加上$k$相当于给$f[n]$乘上$Fibonacci$矩阵^$k$，所以我们可以想到线段树维护矩阵

对于第一个问题：由于矩阵具有分配律，即$a×b+a×c=a×(b+c)$，所以对于一段区间的矩阵可以相加维护。

对于第二个问题，显然将$[l,r]$的矩阵乘上转移矩阵的$x$次方即可。

用线段树维护即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>
#define ll long long
#define re register
#define inf 0x3f3f3f3f
#define ls(k) (k<<1)
#define rs(k) (k<<1|1)
#define mod 1000000007
#define getchar() (p1==p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
using namespace std;
struct node{
    int a[3][3];
    inline void init(){
        a[1][1]=a[2][2]=1;a[1][2]=a[2][1]=0;
    }
    inline void init0(){
        a[1][1]=a[2][2]=a[1][2]=a[2][1]=0;
    }
    inline void init1(){
        a[1][1]=a[2][1]=a[1][2]=1;a[2][2]=0;
    }
    friend node operator + (node aa,node bb){
        for(int i=1;i<=2;i++)
            for(int j=1;j<=1;j++){
                aa.a[i][j]=(aa.a[i][j]+bb.a[i][j]);
                if (aa.a[i][j]>mod)aa.a[i][j]-=mod;
            }
        return aa;
    }
    friend node operator * (node a,node b){
        node c;c.init0();
        for (int i=1;i<=2;++i)
            for (int k=1;k<=2;++k)
                for (int j=1;j<=2;++j){
                    c.a[i][j]+=1ll*a.a[i][k]*b.a[k][j]%mod;
                    if (c.a[i][j]>mod)c.a[i][j]-=mod;
                }
        return c;
    }
    friend node operator ^ (node a,int p){
        node res;
        res.init();
        while(p){
            if(p&1) res=res*a;
            p>>=1;
            a=a*a;
        }
        return res;
    }
}f[100005],p,jz[500005],tag[500005];
inline int read(){
   int x=0,w=0;char ch=getchar();
   while (!isdigit(ch))w|=ch=='-',ch=getchar();
   while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
   return w?-x:x;
}
template <class T>
inline void write(T x) {
    if (x < 0) { putchar('-'); x = -x; }
    T y = 10, len = 1;
    while (y <= x) { y *= 10; ++len; }
    while (len--) { y /= 10; putchar(x / y + 48); x %= y; }
}
inline bool check(node tag){
    return tag.a[1][1]!=1||!tag.a[2][2]!=1||tag.a[1][2]!=0||tag.a[2][1]!=0;
}
inline void pushup(int k){
    jz[k]=jz[ls(k)]+jz[rs(k)];
}
void build(int k,int l,int r){
    tag[k].init();
    if (l==r){
        jz[k]=f[l];
        return;
    }
    int mid=l+r>>1;
    build(ls(k),l,mid);
    build(rs(k),mid+1,r);
    pushup(k);
}
inline void pushdown(int k){
    node sq=tag[k];
    jz[ls(k)]=sq*jz[ls(k)];
    tag[ls(k)]=tag[ls(k)]*sq;
    jz[rs(k)]=sq*jz[rs(k)];
    tag[rs(k)]=tag[rs(k)]*sq;
    tag[k].init();
}
void change(int k,int l,int r,int x,int y,node sq){
    if (x<=l&&r<=y){
        jz[k]=sq*jz[k];
        tag[k]=tag[k]*sq;
        return;
    }
    int mid=l+r>>1;
    if (check(tag[k]))pushdown(k);
    if (x<=mid)change(ls(k),l,mid,x,y,sq);
    if (mid<y) change(rs(k),mid+1,r,x,y,sq);
    pushup(k);
}
node query(int k,int l,int r,int x,int y){
    if (x<=l&&r<=y)
        return jz[k];
    int mid=l+r>>1;
    if (check(tag[k]))pushdown(k);
    if (x<=mid&&mid<y)
        return query(ls(k),l,mid,x,y)+query(rs(k),mid+1,r,x,y);
    else if (x<=mid)return query(ls(k),l,mid,x,y);
    else return query(rs(k),mid+1,r,x,y);
}
signed main(){
    int n=read(),m=read();
    p.init1();
    node ttt;
    ttt.a[1][1]=ttt.a[2][1]=1;
    for (int i=1;i<=n;++i){
        int x=read()-2;
        if (x==-1)f[i].a[1][1]=1,f[i].a[2][1]=0;
        else f[i]=(p^x)*ttt;
    }
    build(1,1,n);
    while (m--){
        int opt=read(),x=read(),y=read();
        if (opt==1){
            int d=read();
            change(1,1,n,x,y,p^d);
        }else{
            node ans=query(1,1,n,x,y);
            write(ans.a[1][1]);puts("");
        }
    }
    return 0;
}